"""
111. 二叉树的最小深度
简单
相关标签
premium lock icon
相关企业
给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。



示例 1：


输入：root = [3,9,20,null,null,15,7]
输出：2
示例 2：

输入：root = [2,null,3,null,4,null,5,null,6]
输出：5


提示：

树中节点数的范围在 [0, 105] 内
-1000 <= Node.val <= 1000
"""
from typing import Optional


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    #从底向上
    def minDepth(self, root: Optional[TreeNode]) -> int:
        #两边不可用取0
        if root==None:
            return 0
        leftD = self.minDepth(root.left)
        rightD = self.minDepth(root.right)
        #一边不可用取另一边
        if leftD==0 and rightD!=0:
            return rightD+1
        if leftD!=0 and rightD==0:
            return leftD+1
        #两边可用去取最短
        return min(leftD, rightD) + 1
    #自顶向下
    def minDepth_2(self, root: Optional[TreeNode]) -> int:
        #自顶向下
        ans = float('inf')
        def dfs(node:Optional[TreeNode],dept:int) -> None:
            #防止有一边的情况，另一边会走到空
            if node is None:
                return
            dept+=1
            nonlocal ans
            #剪枝
            if dept>=ans:
                return
            #如果两边都没有结点，则认为当前是叶子
            if node.left is None and node.right is None:
                ans = min(ans,dept)
            else:
                dfs(node.left,dept)
                dfs(node.right,dept)
        dfs(root,0)
        return ans if ans != float('inf') else 0



if __name__ == '__main__':
    root = TreeNode(2)
    root.right = TreeNode(3)
    root.right.right = TreeNode(4)
    root.right.right.right = TreeNode(5)
    root.right.right.right.right = TreeNode(6)
    # print(Solution().minDepth(root))
    print(Solution().minDepth_2(root))
    print(Solution().minDepth_2(None))